package com.example.lcpractice.dynamic;

/**
 * @author hd
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        //物品的重量 w(i)
        int[] w = {0, 1, 4, 3};
        //物品的价值 val[i]
        int[] val = {1500, 3000, 2000};
        //背包的容量上限
        int m = 4;
        //物品的个数
        int n = val.length;
        //加1是要留出空的一行一列，否则放第一个物品时会越界
        int[][] v = new int[n + 1][m + 1];
        //记录放入的路径
        int[][] path = new int[n + 1][m + 1];


        //遍历行但跳过第一行
        for (int i = 1; i < v.length; i++) {
            //j 是当前背包的最大容量
            //物品是从0容量开始
            for (int j = 1; j < v[0].length; j++) {

                //放不进去，沿用上面的方案，也就是只放前面 i-1 个物品的方案
                // 第1个i=1, 体积w[1]=1, 允许体积j=1 ，走max函数，1500
                // ······
                // 第1个i=1, 体积w[1]=1, 允许体积j=4 ，走max函数，1500
                //=======================================================
                // 第2个i=2, 体积w[2]=4, 允许体积j=1 ，走v[i-1]函数，1500
                // 第2个i=2, 体积w[2]=4, 允许体积j=2 ，走v[i-1]函数，1500
                // 第2个i=2, 体积w[2]=4, 允许体积j=3 ，走v[i-1]函数，1500
                // 第2个i=2, 体积w[2]=4, 允许体积j=4 ，走max函数，3000
                //=======================================================
                // 第3个i=3, 体积w[3]=3, 允许体积j=1 ，走v[i-1]函数，1500
                // 第3个i=3, 体积w[3]=3, 允许体积j=2 ，走v[i-1]函数，1500
                // 第3个i=3, 体积w[3]=3, 允许体积j=3 ，走max函数，2000
                // 第3个i=3, 体积w[3]=3, 允许体积j=3 ，走max函数，v[i]=2000+v[4-3]=1500

                // 当前物品w[i-1]体积大于允许体积，放不进去,v[i-1]代表上一个放物品所取最大价值
                if (w[i] > j) {
                    v[i][j] = v[i - 1][j];
                } else {  //当前物品体积w[i-1]能放进去
                    //不放当前物品的价值
                    int lastStepValue = v[i - 1][j];
                    // 放入当前物品后价值= 当前物品价值+拼凑价值
                    int putNowValue = val[i - 1] + v[i - 1][j - w[i]];
                    //不放i,直接取上一步比放i更好
                    if (lastStepValue > putNowValue) {
                        v[i][j] = lastStepValue;
                    } else {
                        v[i][j] = putNowValue;
                        //在这个地方标记为1，因为在这里才是真正的新加入了一个物品！
                        path[i][j] = 1;
                    }
                }
            }
        }

        for (int[] ints : v) {
            for (int j = 0; j < v[0].length; j++) {
                System.out.print(ints[j] + "\t");
            }
            System.out.println();
        }
        System.out.println("============================");

//        输出最后我们是放入的哪些商品
//        遍历path, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入
//		for(int i = 0; i < path.length; i++) {
//			for(int j=0; j < path[i].length; j++) {
//				if(path[i][j] == 1) {
//					System.out.printf("第%d个商品放入到背包\n", i);
//				}
//			}
//		}


        //动脑筋
        int i = path.length - 1; //行的最大下标
        int j = path[0].length - 1;  //列的最大下标
        while (i > 0 && j > 0) { //从path的最后开始找
            if (path[i][j] == 1) {
                System.out.printf("第%d个商品放入到背包\n", i);
                j -= w[i]; //w[i-1]。j为什么要减掉当前物品的容量呢，因为要把这个物品从包里拿出去，再看看剩下的物品是什么！
            }
            i--;//表示减少物品，已经访问完了，如果放了i进去，就会在上面输出，没放就不管了
        }
    }
}